package com.salim.leetcode.$106;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
    //用后根和中根构造树
    //先倒着遍历后根 第一个肯定是根节点
    //找到中根数组中的那个节点 节点左边是他的左树 右边是他的右树
    //先递归右子树范围和下一个根 再递归左子树范围和下一个根
    //如何优化？做一个中根的值和index的mapping 可以去掉循环
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return loop(postorder,inorder,postorder.length-1,0,inorder.length-1);
    }

    public TreeNode loop(int[] postorder, int[] inorder,int postStart,int inStart,int inEnd) {
        if(inStart>inEnd||inStart<0||inStart>=inorder.length ||postStart<0){
            return null;
        }

        for(int i=inStart;i<=inEnd;i++){
            if(inorder[i]==postorder[postStart]){
                TreeNode result = new TreeNode(postorder[postStart]);
                result.right = loop(postorder,inorder,postStart-1,i+1,inEnd);
                //右树的范围是i+1 - inEnd 长度是 inEnd -i 后根的顺序是 左-右-根 所以左根一定出现在右-根之前
                result.left = loop(postorder,inorder,postStart-1-inEnd+i,inStart,i-1);
                return result;
            }
        }

        return null;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
